package 算法.图.无向图;

import edu.princeton.cs.algs4.IndexMinPQ;
import 算法.图.util.Edge;
import 算法.背包.Bag;

/**
 * 【最小生成树：Prim算法：即时实现】
 * 		
 * @Date   2017-09-04 0:57
 * @author Administrator
 * @version TODO:>>>>>>>尚未测试
 */
public class PrimMST {
	private EdgeWeightedGraph G;	//无向图
	private boolean[] marked;		//保存加入最小生成树的节点
	private IndexMinPQ<Edge> pq;	//索引优先队列(换成List亦可)，小谷堆,保存当前二分时的有效横边
	private Edge[]   edgeTo;		//就是pq当中的每条边
	private double[] distTo;		//就是pd当中的每条边的权值
	public PrimMST(EdgeWeightedGraph G) {
		this.G = G;
		this.marked = new boolean[G.V];
		this.pq = new IndexMinPQ<Edge>(G.V);
		this.edgeTo = new Edge[G.V];
		this.distTo = new double[G.V];
		
		for (int i = 0; i < G.V; i ++)	distTo[i] = Double.POSITIVE_INFINITY;	//初始化，给个最大值
		pq.insert(0, new Edge(0, 0, 0.0d));
		distTo[0] = 0d; 
		
		while (!pq.isEmpty())	visit(pq.delMin());
	}
	
	private void visit(int v) {
		marked[v] = true;
		for(Edge edge : G.adj[v]) {
			int w = edge.other(v);
			if (marked[w])				continue;
			if (edge.weight < distTo[v]) {
				edgeTo[w] = edge;
				distTo[w] = edgeTo[w].weight;
				if (pq.contains(v))		pq.change(w, edge);
				else 					pq.insert(w, edge);
			}
		}
	}
}

